package com.itheima.leetcode.od.b.violentenumeration;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * (B卷,100分)- 数大雁（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 一群大雁往南飞，给定一个字符串记录地面上的游客听到的大雁叫声，请给出叫声最少由几只大雁发出。
 * <p>
 * 具体的：
 * <p>
 * 大雁发出的完整叫声为”quack“，因为有多只大雁同一时间嘎嘎作响，所以字符串中可能会混合多个”quack”。
 * <p>
 * 大雁会依次完整发出”quack”，即字符串中’q’ ,‘u’, ‘a’, ‘c’, ‘k’ 这5个字母按顺序完整存在才能计数为一只大雁。如果不完整或者没有按顺序则不予计数。
 * <p>
 * 如果字符串不是由’q’, ‘u’, ‘a’, ‘c’, ‘k’ 字符组合而成，或者没有找到一只大雁，请返回-1。
 * <p>
 * 输入描述
 * <p>
 * 一个字符串，包含大雁quack的叫声。1 <= 字符串长度 <= 1000，字符串中的字符只有’q’, ‘u’, ‘a’, ‘c’, ‘k’。
 * <p>
 * 输出描述
 * <p>
 * 大雁的数量
 * <p>
 * 用例
 * <p>
 * 输入	quackquack
 * <p>
 * 输出	1
 * 说明	无
 * <p>
 * 输入	qaauucqckk
 * <p>
 * 输出	-1
 * 说明	无
 * <p>
 * 输入	quacqkuac
 * <p>
 * 输出	1
 * 说明	无
 * <p>
 * 输入	qququaauqccauqkkcauqqkcauuqkcaaukccakkck
 * <p>
 * 输出	5
 * 说明	无
 */
public class CountingGeese {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);
        String quack = sc.next();*/

        String quack = "qququaauqccauqkkcauqqkcauuqkcaaukccakkckk";
        System.out.println(getResult(quack));
        System.out.println(getResult2(quack));
    }

    public static int getResult(String quack) {
        LinkedList<Integer> q = new LinkedList<>();

        int u = 0;
        int a = 0;
        int c = 0;

        ArrayList<Integer[]> ranges = new ArrayList<>();

        for (int i = 0; i < quack.length(); i++) {
            switch (quack.charAt(i)) {
                case 'q':
                    q.add(i);
                    break;
                case 'u':
                    if (u + 1 <= q.size()) {
                        u++;
                    }
                    break;
                case 'a':
                    if (a + 1 <= u) {
                        a++;
                    }
                    break;
                case 'c':
                    if (c + 1 <= a) {
                        c++;
                    }
                    break;
                case 'k':
                    if (c >= 1) {
                        ranges.add(new Integer[]{q.removeFirst(), i});
                        u--;
                        a--;
                        c--;
                    }
                    break;
                default:
                    return -1;
            }
        }

        if (ranges.size() == 0) {
            return -1;
        }

        int ans = 1;
        for (int i = 0; i < ranges.size(); i++) {
            int count = 1;
            for (int j = i + 1; j < ranges.size(); j++) {
                if (ranges.get(i)[1] >= ranges.get(j)[0]) {
                    count++;
                }
            }
            ans = Math.max(ans, count);
        }

        return ans;
    }

    /**
     * 穷举（找到一只就全部替换成空格字符）
     *
     * @param quack
     * @return
     */
    public static int getResult2(String quack) {
        char[] quacks = quack.toCharArray();

        int count = 0;
        while (find(quacks)) {
            count++;
        }

        // 如果没有找到一只大雁，请返回-1。
        return count == 0 ? -1 : count;
    }

    public static boolean find(char[] quacks) {
        boolean isFind = false;

        int index = 0;
        int[] quack_index = new int[5];

        for (int i = 0; i < quacks.length; i++) {
            if (quacks[i] == "quack".charAt(index)) {
                quack_index[index++] = i;
            }

            if (index == 5) {
                isFind = true;

                for (int j : quack_index) {
                    quacks[j] = ' ';
                }

                index = 0;
            }
        }

        return isFind;
    }
}